struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

class MyLinkedList {
public:
    MyLinkedList() {
        size=0;
        head=new ListNode(0);
    }
    
    int get(int index) {
        if(index<0||index>=size)//* 记得检查索引是符合条件
            return -1;
        ListNode* temp=head;
        for (int i = 0; i <= index; i++)
        {
            temp=temp->next;
        }
        return temp->val;
    }
    //* 其实头插和尾插都可以用addAtIndex实现
    void addAtHead(int val) {
        ListNode* tempnode=new ListNode(0);
        tempnode->val=val;
        tempnode->next=head->next;
        head->next=tempnode;
        size++;
    }
    
    void addAtTail(int val) {
        ListNode* tempnode=new ListNode(0);
        ListNode *tempptr=head;
        for (int i = 0; i < size; i++)
            tempptr=tempptr->next;
        tempnode->val=val;
        tempptr->next=tempnode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index<0||index>size)//*检查索引合理性
        //!注意这里index可以等于size，因为是现有大小的下一个位置，即尾插
        //!index从0开始，size从1开始，所以正好相等
            return;
        ListNode* tempnode=new ListNode(0);
        ListNode *tempptrpre=head;
        for (int i = 0; i < index; i++)
            tempptrpre=tempptrpre->next;
        //tempptrrear=tempptrpre->next;
        tempnode->val=val;
        tempnode->next=tempptrpre->next;
        tempptrpre->next=tempnode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>=size)
            return;
        ListNode *tempptrpre=head,*tempptrdelete;
        for (int i = 0; i < index; i++)
            tempptrpre=tempptrpre->next;
        tempptrdelete=tempptrpre->next;
        tempptrpre->next=tempptrdelete->next;
        delete tempptrdelete;
        size--;
    }

    int size;
    ListNode *head;
};